/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***普通二叉树（非有序二叉树）的创建、递归和查找、删除节点    P94 ***/
/***C++ 实现版本    written by Daniel           ***/

#include <iostream>
#include <string>

using std::cout;
using std::endl;
using std::string;

class HeroNode
{
public:
	HeroNode() = delete;
	//构造函数
	HeroNode(int id, string name, HeroNode *left, HeroNode *right) : id(id), name(name), left(left), right(right) {}
	HeroNode(int id, string name) : id(id), name(name), left(nullptr), right(nullptr) {}
	//删除拷贝构造
	HeroNode(HeroNode &) = delete;
	string transToString()
	{
		// cout << "id=" << id << ",name=" << name << endl;
		return string("id=" + std::to_string(id) + "\t" + "name=" + name);
	}
	int getId()
	{
		return this->id;
	}
	void setId(int id)
	{
		this->id = id;
	}
	string getName()
	{
		return this->name;
	}
	void setName(string name)
	{
		this->name = name;
		return;
	}
	HeroNode *getLeft()
	{
		return this->left;
	}
	void setLeft(HeroNode *left)
	{
		this->left = left;
		return;
	}
	HeroNode *getRight()
	{
		return this->right;
	}
	void setRight(HeroNode *right)
	{
		this->right = right;
		return;
	}
	int getLeftType()
	{
		return leftType;
	}
	void setLeftType(int value)
	{
		this->leftType = value;
	}
	int getRightType()
	{
		return rightType;
	}
	void setRightType(int value)
	{
		this->rightType = value;
	}
	//前序遍历
	void preOrder()
	{
		cout << this->transToString() << endl;
		if (this->left != nullptr)
		{
			this->left->preOrder();
		}
		if (this->right != nullptr)
		{
			this->right->preOrder();
		}
		return;
	}
	//中序遍历
	void midOrder()
	{
		if (this->left != nullptr)
		{
			this->left->midOrder();
		}
		cout << this->transToString() << endl;
		if (this->right != nullptr)
		{
			this->right->midOrder();
		}
	}
	//后序遍历
	void postOrder()
	{
		if (this->left != nullptr)
		{
			this->left->postOrder();
		}
		if (this->right != nullptr)
		{
			this->right->postOrder();
		}
		cout << this->transToString() << endl;
		return;
	}
	//前序查找，中序查找和后序查找
	HeroNode *preFind(int id)
	{
		if (this->id == id)
		{
			cout << "节点已经找到，信息为如下：" << endl;
			// cout<<this->transToString()<<endl;
			return this;
		}
		HeroNode *resNode = nullptr;
		if (this->left != nullptr)
		{
			resNode = this->left->preFind(id);
			if (resNode != nullptr)
			{
				return resNode;
			}
		}

		if (this->right != nullptr)
		{
			resNode = this->right->preFind(id);
		}
		return resNode;
	}
	HeroNode *midFind(int id)
	{
		HeroNode *resNode = nullptr;
		if (this->left != nullptr)
		{
			resNode = this->left->preFind(id);
			if (resNode != nullptr)
			{
				return resNode;
			}
		}
		if (this->id == id)
		{
			return this;
		}
		if (this->right != nullptr)
		{
			resNode = this->right->preFind(id);
		}
		return resNode;
	}
	HeroNode *postFind(int id)
	{
		HeroNode *resNode = nullptr;
		if (this->left != nullptr)
		{
			resNode = this->left->preFind(id);
		}
		if (this->right != nullptr)
		{
			resNode = this->right->preFind(id);
			if (resNode != nullptr)
			{
				return resNode;
			}
		}
		if (this->id == id)
		{
			return this;
		}
		return resNode;
	}
	//节点删除函数
	void delNode(int id)
	{
		//判断当前节点下一个节点是否是要被删除的节点
		//判断当前节点的左子节点是否是被删除的节点
		if ((this->getLeft() != nullptr) && (this->getLeft()->getId() == id))
		{
			delete this->getLeft();
			this->left = nullptr;
			return;
		}
		//判断当前节点的右子节点是否是被删除的节点
		if ((this->getRight() != nullptr) && (this->getRight()->getId() == id))
		{
			delete this->getRight();
			this->right = nullptr;
			return;
		}
		//递归向下查找
		if (this->left != nullptr)
		{
			this->left->delNode(id);
		}
		if (this->right != nullptr)
		{
			this->right->delNode(id);
		}
	}
	//这个析构有点难度~~~ 使用后序遍历来释放二叉树
	~HeroNode()
	{
		//线索化二叉树的析构
		if ((this->left == nullptr||this->leftType==1) && (this->right == nullptr||this->rightType==1))
		{
			return;
		}
		if (this->left != nullptr)
		{
			delete this->left;
			this->left = nullptr;
		}
		if (this->right != nullptr)
		{
			delete right;
			right = nullptr;
		}
	}

private:
	int id;
	string name;
	HeroNode *left;
	HeroNode *right;
	// leftType==0，代表left指向左子树，如果为1，表示指向前驱节点；
	// rightType==0，代表right指向右子树，如果为1，表示指向后继节点；
    //默认情况下  需要赋值为0  mingw32-make的要求！！！
    //否则，mingw编译器会给一个非0的任意值 
	int leftType=0;
	int rightType=0;
};
//创建一棵二叉树
class BinaryTree
{
public:
	BinaryTree() : root(nullptr) {}
	BinaryTree(HeroNode *root) : root(root) {}
	BinaryTree(BinaryTree &) = delete;
	HeroNode *getRoot()
	{
		return this->root;
	}
	void setRoot(HeroNode *root)
	{
		this->root = root;
	}
	//编写对二叉树进行中序线索化的方法
	/*
		功能：线索化二叉树
		参数：node，二叉树的根节点；
		返回值：空
	*/
	void threadedNodes(HeroNode *node)
	{
		if (node == nullptr)
		{
			return;
		}
		//中序线索化左子树
		threadedNodes(node->getLeft());
		//中序线索化当前节点
		if (node->getLeft() == nullptr)
		{
			node->setLeft(preNode);
			node->setLeftType(1);
		}
		if (preNode != nullptr && preNode->getRight() == nullptr)
		{
			preNode->setRight(node);
			preNode->setRightType(1);
		}
		// preNode相当于类的全局变量
		preNode = node;
		//中序线索化右子树
		threadedNodes(node->getRight());
	}
	//对线索化的二叉树进行中序遍历
	void threadedMidOrder()
	{
		//先找到中序遍历的起点
		HeroNode *node = this->root;
		while (node != nullptr)
		{
			while (node->getLeftType() == 0)
			{
				node = node->getLeft();
			}
			//打印这个节点
			cout << node->transToString() << endl;
			while (node->getRightType() == 1) {
				node = node->getRight();
				cout << node->transToString() << endl;
			}
			node = node->getRight();
		}
	}

	//二叉树的前中后序遍历
	void preOrder()
	{
		if (root != nullptr)
		{
			this->root->preOrder();
		}
		else
		{
			cout << "当前二叉树为空，无法遍历！" << endl;
		}
	}
	void midOrder()
	{
		if (root != nullptr)

		{
			this->root->midOrder();
		}
		else
		{
			cout << "当前二叉树为空，无法遍历！" << endl;
		}
	}
	void postOrder()
	{
		if (root != nullptr)

		{
			this->root->postOrder();
		}
		else
		{
			cout << "当前二叉树为空，无法遍历！" << endl;
		}
	}
	HeroNode *preFind(int id)
	{
		return root->preFind(id);
	}
	HeroNode *midFind(int id)
	{
		return root->midFind(id);
	}
	HeroNode *postFind(int id)
	{
		return root->postFind(id);
	}
	void delNode(int id)
	{
		if (root == nullptr)
		{
			cout << "当前二叉树为空，无法删除" << endl;
			return;
		}
		else if (root->getId() == id)
		{
			delete root;
		}
		else
		{
			root->delNode(id);
		}
		return;
	}
	//二叉树的析构！我的神呐~~~
	~BinaryTree()
	{
		if (root != nullptr)
		{
			delete root;
			root = nullptr;
		}
	}

private:
	HeroNode *root;
	HeroNode *preNode = nullptr;
};

int main()
{
	HeroNode *node1 = new HeroNode(1, "daniel");
	HeroNode *node2 = new HeroNode(3, "gary");
	HeroNode *node3 = new HeroNode(6, "alice");
	HeroNode *node4 = new HeroNode(8, "maria");
	HeroNode *node5 = new HeroNode(10, "Jason");
	HeroNode *node6 = new HeroNode(14, "smith");
	node1->setLeft(node2);
	node1->setRight(node3);
	node2->setLeft(node4);
	node2->setRight(node5);
	node3->setLeft(node6);
	BinaryTree *newTree = new BinaryTree(node1);
	newTree->threadedNodes(newTree->getRoot());
	HeroNode *tempNode = node5->getLeft();
	if (tempNode != nullptr)
	{
		cout << tempNode->transToString() << endl;
	}
	HeroNode *tempNode2 = node5->getRight();
	if (tempNode2 != nullptr)
	{
		cout << tempNode2->transToString() << endl;
	}
	//中序线索化结果
	cout << "中序线索化 中序遍历结果" << endl;
	newTree->threadedMidOrder();
	delete newTree;
	return 0;
}